package a_doubleWrite;

/**
 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * @author: luolidong
 * @create: 2021-07-17 19:19
 * @version: 1.0
 */
public class L42 {
    public int trap(int[] height) {
        if(height.length<=2) return 0;
        int len=height.length;
        //从左先右，求最高左边界
        int[] leftHeight=new int[len];
        leftHeight[0]=height[0];
        for (int i = 1; i <len ; i++) {
            leftHeight[i]=Math.max(leftHeight[i-1],height[i]);
        }
        //从右先左，求最高右边界
        int[] rightHeight=new int[len];
        rightHeight[len-1]=height[len-1];
        for (int i = len-2; i >=0 ; i--) {
            rightHeight[i]=Math.max(rightHeight[i+1],height[i]);
        }
        int ans=0;
        //取左右边界较小值
        for (int i = 0; i < len; i++) {
            ans+=Math.min(rightHeight[i],leftHeight[i])-height[i];
        }
        return ans;
    }
}
